#include "shellSort.h"

//Shell排序通过比较相隔一段距离的元素来工作，各趟比较所用的距离随着算法的进行而减小，
//直到比较相邻元素的最后一趟排序为止
//最常用的序列是H=N/2
void ShellSort(ElementType A[], int N)
{
    int i, j, increment;
    ElementType Tmp;
    for (increment = N / 2; increment > 0; increment /= 2)
    {
        //取出排序数组的元素，开始尝试从指定的元素开始交换对应位置的元素，将指定间隔间的数进行排序
        //由于我们是从左往右一次取间隔数据，就如同插入排序一般，能够保证再间隔间的元素是排过序的
        for (i = increment; i < N; i++)
        {
            //缓存即将排序的数据，在排序的过程中可能需要将这个数据移到前面
            Tmp = A[i];
            //和前面的数列进行比较，前面的数列肯定经过了插入排序，是有顺序性的
            for (j = i; j >= increment; j -= increment)
                //发现比前面的数小，将前面的数后移，让出位置给本数
                if (Tmp < A[j - increment])
                    A[j] = A[j - increment];
                else
                    //如果比前面的数大，那么就确定此数的位置了
                    break;
            //将此数安插到正确的位置
            A[j] = Tmp;
        }
    }
}